package com.kevin.algorithm;

import com.kevin.model.Location;
import com.kevin.utils.DistanceUtil;
import com.kevin.utils.MapUtils;
import com.kevin.utils.PointsRep;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;

/**
 * @Description: 模拟退火算法
 *
 * @author kevin
 * @version V1.0
 * @date 2019/3/15 15:50
 **/
public class SimulateAnnealRoute implements AlgorithmStrategy{
    private static final Logger LOGGER = LoggerFactory.getLogger(SimulateAnnealRoute.class);

    /**
     * 最好排列
     */
    private List<Location> bestLocation = new ArrayList<>();
    /**
     * 最好距离
     */
    private BigDecimal bestDis;
    /**
     * 当前距离
     */
    private BigDecimal currDis;
    /**
     * 衰减距离
     */
    private BigDecimal annealDis;
    /**
     * 外循环次数
     */
    private static final Integer outInterval = 30;
    /**
     * 衰减次数
     */
    private static final Integer inInterval = 150;
    /**
     * 衰减比率
     */
    private static final BigDecimal delta = new BigDecimal(0.7);
    /**
     * 数据仓库
     */
    private PointsRep pointsRep;

    @Override
    public Location[][] execute(PointsRep pointsRep) {
        this.pointsRep = pointsRep;
        List<Location> locations = this.pointsRep.getPoints();

        LOGGER.info("模拟退火算法开始：入参个数：{}",locations.size());
        handle(locations);
        LOGGER.info("模拟退火算法结束。");

        Location[][] result = new Location[1][bestLocation.size()];
        for(int i=0;i<bestLocation.size();i++){
            result[0][i] = bestLocation.get(i);
        }

        return result;
    }

    /**
     * 数据处理
     */
    private void handle(List<Location> locations){
        /**
         * 将初始值封装为最优值
         * 最优队列
         * 最优路径
         */
        for(Location item : locations){
            bestLocation.add(item);
        }
        /*
            将起止位置加入队列，计算距离
         */
        locations.add(0,this.pointsRep.getBegin());
        locations.add(this.pointsRep.getEnd());
        bestDis = MapUtils.getListDis(locations);
        currDis = new BigDecimal(bestDis.doubleValue());
        annealDis = new BigDecimal(bestDis.doubleValue());

        //执行模拟退火算法
        simulateAnneal(locations);
    }

    /**
     * 模拟退火算法
     */
    private void simulateAnneal(List<Location> locations){
        /*
            循环所有元素，不包含起止点
         */
        for(int i=0;i<outInterval;i++){
            for(int j=0;j<inInterval;j++){

                /*
                    产生第一个随机数
                 */
                int ranIndexX = (int) (Math.random()*(locations.size()));
                while(ranIndexX == 0 || ranIndexX == (locations.size()-1)){
                    ranIndexX = (int) (Math.random()*locations.size());
                }

                /*
                    产生第二个随机数
                 */
                int ranIndexY = (int) (Math.random()*(locations.size()));
                while(ranIndexY == 0 || ranIndexY == (locations.size()-1) || ranIndexY == ranIndexX){
                    ranIndexY = (int) (Math.random()*locations.size());
                }

                BigDecimal changeBefDis = new BigDecimal(0);
                BigDecimal changeAftDis = new BigDecimal(0);
                /*
                    判断随机点和当前点是否相邻
                    然后计算交换前后距离变化的差值
                 */
                if(Math.abs(ranIndexX-ranIndexY) == 1){
                    if(ranIndexX > ranIndexY){
                        //交换前
                        changeBefDis = DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexY-1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexX+1)));
                        //交换后
                        changeAftDis = DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexX+1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexY-1)));
                    }else{
                        //交换前
                        changeBefDis = DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexX-1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexY+1)));
                        //交换后
                        changeAftDis = DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexY+1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexX-1)));
                    }
                }else{
                    //交换前
                    changeBefDis = DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexX-1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexX+1))).add(DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexY-1))).add(DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexY+1)));
                    //交换后
                    changeAftDis = DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexX-1)).add(DistanceUtil.algorithmBig(locations.get(ranIndexY),locations.get(ranIndexX+1))).add(DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexY-1))).add(DistanceUtil.algorithmBig(locations.get(ranIndexX),locations.get(ranIndexY+1)));
                }

                //计算交换前后差值
                BigDecimal minusResult = new BigDecimal(0);
                if(changeAftDis.compareTo(changeBefDis) != 0){
                    minusResult = changeAftDis.subtract(changeBefDis);
                }
                //计算交换概率
                double changeParam = 1;
                if(minusResult.compareTo(new BigDecimal(0)) != 0){
                    changeParam = Math.exp(-minusResult.doubleValue()/annealDis.doubleValue());
                }

                //判断是否需要交换两点
                if(minusResult.compareTo(new BigDecimal(0)) < 0) {
                    Collections.swap(locations, ranIndexX, ranIndexY);
                    currDis = currDis.add(minusResult);
                }else if(changeParam > Math.random()){
                    Collections.swap(locations, ranIndexX, ranIndexY);
                    currDis = currDis.add(minusResult);
                    //路径衰减
                    annealDis = annealDis.multiply(delta);
                }
            }

            if(currDis.compareTo(bestDis) < 0){
                for(int n = 1;n < (locations.size()-1);n++){
                    bestLocation.set((n-1),locations.get(n));
                }

                bestDis = new BigDecimal(currDis.doubleValue());
                annealDis = new BigDecimal(currDis.doubleValue());
            }
        }
    }
}
